π κ·Έλν
κ³μΈ΅μ μΈ κ΅¬μ‘°λ³΄λ€ μ’ λ μΌλ°μ μ΄κ³ κ°λ ₯ν μλ£ κ΅¬μ‘°, μ¬λ¬Όμ΄λ κ°λ κ°μ μ°κ²° ꡬ쑰 ex. μ¬λ¬ λμλ€μ μ°κ²°νλ λλ‘λ§, μ¬λλ€ κ°μ μ§μΈ κ΄κ³, μΉ μ¬μ΄νΈ κ°μ λ§ν¬
νΈλ¦¬μ μμλ λΆλͺ¨ μμ κ΄κ³μ λν μ μ½μ΄ μμ΄ μ’ λ λ€μνκ³ μμ λ‘μ΄ κ΅¬μ‘° ννμ΄ κ°λ₯νλ€.
π‘ μ μ
κ·Έλν G(V, E)λ μ΄λ€ μλ£λ κ°λ μ νννλ μ μ (vertex)λ€μ μ§ν© Vμ μ΄λ€μ μ°κ²°νλ κ°μ (edge)λ€μ μ§ν© Eλ‘ κ΅¬μ±λ μλ£ κ΅¬μ‘°
- μ μ μ μμΉ μ 보λ κ°μ μ μμ λ±μ κ·Έλνμ μ μμ ν¬ν¨λμ§ μλλ€.
π‘ μ’ λ₯
νννκ³ μ νλ λμμ λ°λΌ μ¬λ¬ κ°μ§ λ³νλ ννλ₯Ό κ°μ§ μ μλ€.
λ°©ν₯ κ·Έλν(directed graph) or μ ν₯ κ·Έλν
κ° κ°μ μ΄ βλ°©ν₯β μ΄λΌλ μλ‘μ΄ μμ±μ κ°μ§λ€. μ¦, λ°©ν₯μ λ°λΌ μλ‘μ΄ κ°μ μΌλ‘ λΆλ₯λλ€. ex. μ¬λλ€ κ°μ μ§μ¬λ κ΄κ³, λλ‘μμμ μΌλ°© ν΅ν λ±
무ν₯ κ·Έλν(undirected graph) κ°μ μ λ°©ν₯μ΄ μλ κ·Έλν
κ°μ€μΉ κ·Έλν(weighted graph)
κ° κ°μ μ βκ°μ€μΉβ λΌλ μ€μ μμ±μ΄ μΆκ°λλ€. ex. λ λμ μ¬μ΄μ 거리, λ 물건 μ¬μ΄μ κ΅ν λΉμ¨ λ±
μ΅μ μ€ν¨λ νΈλ¦¬μ μ΅λ¨ κ²½λ‘ λ¬Έμ μμ μ€μν κ°λ μΌλ‘ μ¬μ©λλ€!
λ€μ€ κ·Έλν(multigraph)
λ μ μ μ¬μ΄μ λ κ° μ΄μμ κ°μ μ΄ μμ μ μλ κ·Έλν
λ¨μ κ·Έλν(simple graph)
λ μ μ μ¬μ΄μ μ΅λ ν κ°μ κ°μ λ§ μλ κ·Έλν
π νΈλ¦¬ or λ£¨νΈ μλ νΈλ¦¬(unrooted tree)λ λΆλͺ¨ μμ κ΄κ³κ° μμ λΏ, κ°μ λ€μ μ°κ²° κ΄κ³λ§μ 보면 무ν₯ κ·Έλνμ΄λ€. μ¦, κ°μ μ ν΅ν΄ λ μ μ μ μλ λ°©λ²μ΄ λ± νλλΏμμ μλ―Ένλ€.
μ΄λΆ κ·Έλν(bipartite graph)
κ·Έλνμ μ μ λ€μ κ²ΉμΉμ§ μλ λ κ°μ κ·Έλ£ΉμΌλ‘ λλ μ μλ‘ λ€λ₯Έ κ·Έλ£Ήμ μν μ μ λ€ κ°μλ§ κ°μ μ΄ μ‘΄μ¬νλλ‘ λ§λ€ μ μλ κ·Έλν ex. ννΈ μκ·Έλκ³Ό κ°μ νλ‘κ·Έλ¨μμμ μ¬λμ μλκΈ°
- κ°μ κ·Έλ£Ήμ μ μ λ€ κ°μλ κ°μ μ΄ μλ€.
μ¬μ΄ν΄ μλ λ°©ν₯ κ·Έλν(directed acyclic graph) = DAG
ν μ μμ μΆλ°ν΄ λ€μ μκΈ° μμ μΌλ‘ λμμ€λ κ²½λ‘κ° μλ, μ¦ cycleμ΄ μλ λ°©ν₯ κ·Έλν ex. μ¬λ¬ μμ λ€ κ°μ μνΈ μμ‘΄ κ΄κ³
- κ°μ μ λ°©ν₯μ 무μν κ²½μ° cycleμ΄ μ‘΄μ¬ν μλ μλ€.
π‘ κ²½λ‘
λκ³Ό λμ΄ μλ‘ μ°κ²°λ κ°μ λ€μ μμλλ‘ λμ΄ν κ²
λ¨μ κ²½λ‘
κ²½λ‘ μ€ ν μ μ μ μ΅λ ν λ²λ§ μ§λλ κ²½λ‘
μ¬μ΄ν΄(cycle)
μμν μ μμ λλλ κ²½λ‘
π‘ νν λ°©λ²
μ¬λ¬ κ°μ²΄λ€μ΄ μλ‘ μ°κ²°λμ΄ μλ€λ μ μ νΈλ¦¬μ ν° μ°¨μ΄κ° μλ€.
- κ° μ μ μ κ°μ²΄λ‘ νν
- κ° κ°μ²΄κ° μμ κ³Ό κ°μ μΌλ‘ μ°κ²°λ μ μ λ€μ λν μ 보μ λͺ©λ‘μ μ μ₯
λλ€μμ κ²½μ°, κ·Έλνλ νΈλ¦¬μ λΉν΄ ν¨μ¬ μ μ μΈ μ©λλ‘ μ¬μ©λλ€.
- μλ‘μ΄ μ μ μ΄λ κ°μ μ μΆκ°νκ³ μμ νλ μΌμ΄ μμ£Ό μΌμ΄λμ§ μλλ€λ μλ―Έ
- λ°λΌμ, ꡬ쑰μ λ³κ²½μ΄ μ΄λ ΅λλΌλ μ’ λ κ°λ¨νκ³ λ©λͺ¨λ¦¬λ₯Ό μ κ² μ°¨μ§νλ λ°©λ²μΌλ‘ ꡬννλ€.
κ°λ¨ν λ°©λ²
- κ·Έλνμ μ μ λ€μ κ°μ²΄μ instanceλ‘ νννλ λμ κ° μ μ μ 0λΆν° μμνλ λ²νΈλ₯Ό λΆμ΄κ³ ,
- λ°°μ΄μ κ° μ μ μ μ 보λ₯Ό μ μ₯
- κ°μ μ λ°λμͺ½ μ μ μ λ²νΈλ₯Ό μ μ₯νλ λ°©μμΌλ‘ ꡬν
μΈμ 리μ€νΈ
κ·Έλνμ κ° μ μ λ§λ€ ν΄λΉ μ μ μμ λκ°λ κ°μ μ΄ λͺ©λ‘μ μ μ₯νλ λ°©μ β κ·Έλνλ κ° μ μ λ§λ€ νλμ μ°κ²° 리μ€νΈλ₯Ό κ°λ λ°©μμΌλ‘ ꡬν
Java β’ List λ΄λΆμ λμ Listλ₯Ό μ μΈνμ¬ μ²λ¦¬νκ³ ν΄λΉ nodeμ costλ₯Ό Listμ²λΌ μ²λ¦¬νλ κ²½μ°κ° λ§κΈ° λλ¬Έμ, μ΄λ₯Ό κ΄λ¦¬νκΈ° μν Classλ₯Ό μ μΈνμ¬ μ¬μ©νλ€.
class Node {
int node;
int cost;
Node (int node, int cost) {
this.node = node;
this.cost = cost;
}
}
λ¨μ λ μ μ μ΄ μ£Όμ΄μ§ λ μ΄ μ μ μ΄ μ°κ²°λμ΄ μλμ§λ₯Ό μκΈ° μν΄μλ λͺ¨λ μ°κ²° 리μ€νΈλ₯Ό μΌμΌμ΄ νμν΄μΌ νλ€λ κ² β μ΄μ κ°μ μ°μ°μλλ₯Ό λμ΄κΈ° μν΄ μΈμ νλ ¬ (adjacency matrix) νν λ°©μμ μ¬μ©
μΈμ νλ ¬
2μ°¨μ λ°°μ΄μ μ΄μ©ν΄ κ·Έλνμ κ°μ μ 보λ₯Ό μ μ₯
ex. 1 β 2 β’ graph[1][2] = true or cost
β κ°μ₯ κ°λ¨ν ννμ κ²½μ°, 2μ°¨μ boolean κ° λ°°μ΄
λ λ°©μμ λΉκ΅
λ λ°©μμ μ λ°λμ νΉμ§μ κ°μ Έ, μλ‘μ λ¨μ μ΄ μλ‘μ μ₯μ μ΄ λλ€. λ©λͺ¨λ¦¬ κ³΅κ° μΈ‘λ©΄κ³Ό νμ μκ° μΈ‘λ©΄μΌλ‘ λλλ€.
μΈμ 리μ€νΈμ μ₯μ
-
|V| κ°μ μ°κ²° 리μ€νΈμ μ€μ κ°μ μλ§νΌμ μμλ§ μ‘΄μ¬νκΈ°μ O(|V|+|E|) ν¬κΈ°μ 곡κ°λ§ μ¬μ©νλ€.
μΈμ 리μ€νΈμ λ¨μ
-
μ μ μ λ²νΈκ° μ£Όμ΄μ§ κ²½μ°, λ μ μ μ μλ κ°μ μ μ‘΄μ¬λ₯Ό μκΈ° μν΄μλ λͺ¨λ μ°κ²° 리μ€νΈλ₯Ό νμν΄μΌ νλ€.
μΈμ νλ ¬μ μ₯μ
-
μ μ μ λ²νΈκ° μ£Όμ΄μ§ κ²½μ°, λ μ μ μ μλ κ°μ μ μ‘΄μ¬λ₯Ό ν λ²μ λ°°μ΄ μ κ·Όλ§μΌλ‘ μ μ μλ€.
μΈμ νλ ¬μ λ¨μ
- νμ μ μ μ§ν© μ 체λ₯Ό μ μ₯νκΈ° μν 2μ°¨μ λ°°μ΄μ μ¬μ©νκΈ° λλ¬Έμ, νμ O(|V|^2) ν¬κΈ°μ 곡κ°μ μ¬μ©ν΄μΌ νλ€.
κ°μ μ μκ° |V|^2μ λΉν΄ ν¨μ¬ μ μ κ·Έλν: ν¬μ κ·Έλν(sparse graph) β’ μΈμ 리μ€νΈ κ°μ μ μκ° |V|^2μ κ±°μ λΉλ‘νλ κ·Έλν: λ°μ§ κ·Έλν(dense graph) β’ μΈμ νλ ¬
π κΉμ΄ μ°μ νμ (DFS)
κ·Έλνμ λͺ¨λ μ μ μ λ°κ²¬νλ κ°μ₯ λ¨μνκ³ κ³ μ μ μΈ λ°©λ²μΌλ‘, νμ¬ μ μ μμ λ€μ κ°μ§λ‘ λμ΄κ°κΈ° μ μ, ν΄λΉ κ°μ§λ₯Ό λͺ¨λ νμνλ λ°©λ²μ΄λ€.
- νμ¬ μ μ κ³Ό μΈμ ν κ°μ λ€μ νλμ© κ²μ¬
- μμ§ λ°©λ¬Ένμ§ μμ μ μ μΌλ‘ ν₯νλ κ°μ μ΄ μλ€λ©΄ κ·Έ κ°μ μ νμ
- λ μ΄μ κ° κ³³μ΄ μλ κ²½μ°, λ§μ§λ§μ λ°λΌμλ κ°μ μ λ°λΌ λ€λ‘ λμκ°
DFSμμ κ°μ₯ μ€μν νΉμ§μ 3λ²μ΄λ€. μ΄λ₯Ό μν΄μ μ§κΈκΉμ§ κ±°μ³μ¨ μ μ λ€μ μ μ₯ν΄μΌ νλλ°, μ¬κ· νΈμΆμ μ΄μ©νμ¬ κ°λ¨νκ² κ΅¬νν μ μλ€.
μ£Όμν μ κ·Έλνμ λͺ¨λ μ μ λ€μ΄ κ°μ μΌλ‘ μ°κ²°λμ§ μμ κ²½μ°κ° μμ μ μλ€. μ΄λλ λͺ¨λ μ μ λ€μ λ³Ό μ μλ μ½λλ₯Ό μμ±ν μ μμ΄μΌ νλ€.
π‘ μκ° λ³΅μ‘λ
μΈμ 리μ€νΈλ₯Ό μ¬μ©νλ κ²½μ°
- ν μ μ λ§λ€
DFS()λ ν λ²μ© νΈμΆ β |V| λ² - O(|V| + |E|)
μΈμ νλ ¬μ μ¬μ©νλ κ²½μ°
DFS()μ νΈμΆνμλ μΈμ 리μ€νΈμ λμΌνκ² |V| λ²- λ€λ₯Έ λͺ¨λ μ μ μ μννλ©° λ μ μ μ¬μ΄μ κ°μ μ΄ μλκ°λ₯Ό νμΈνλ―λ‘ ν λ²μ O(|V|) μκ°μ΄ μλͺ¨
- O(|V|^2)
π‘ μμ μ λ ¬
μμ‘΄μ±μ΄ μλ μμ λ€μ΄ μ£Όμ΄μ§ λ, μ΄λ€μ μ΄λ€ μμλ‘ μνν΄μΌ νλμ§ κ³μ°
μμ‘΄μ± κ·Έλν(dependency graph) κ° μμ μ μ μ μΌλ‘ νννκ³ , μμ κ°μ μμ‘΄ κ΄κ³λ₯Ό κ°μ μΌλ‘ ννν λ°©ν₯ κ·Έλν β cycleμ΄ μλ λ°©ν₯ κ·Έλν, μ¦ DAG
μμ μ λ ¬
μμ‘΄μ± κ·Έλνμ λͺ¨λ μμ‘΄μ±μ΄ λ§μ‘±λλ €λ©΄, λͺ¨λ κ°μ μ΄ μΌμͺ½μμ μ€λ₯Έμͺ½μΌλ‘ κ°μΌ νλλ°, μ΄λ₯Ό μν΄ DAGμ μ μ μ λ°°μ΄νλ λ¬Έμ
μ§κ΄μ μΈ λ°©λ²
- λ€μ΄μ€λ κ°μ μ΄ νλλ μλ μ μ μ νμ
- μ λ ¬ κ²°κ³Όμ μ΄μ΄ λΆμ΄κΈ°
- κ·Έλνμμ ν΄λΉ μ μ μ μμ μ κ³Όμ μ λ°λ³΅
μ΄λ₯Ό DFS λ₯Ό μ΄μ©ν΄ ν΄κ²°ν μ μλ€.
- ν μ μ μ λν
DFS()κ° μ’ λ£λ λλ§λ€ νμ¬ μ μ μ λ²νΈλ₯Ό κΈ°λ‘ - λͺ¨λ νμμ΄ λλ ν, μ μ λ²νΈλ€μ λ€μ§μΌλ©΄ μμ μ λ ¬ κ²°κ³Ό
π‘ μ΄λ‘ μ λ°°κ²½κ³Ό μμ©
κΉμ΄ μ°μ νμκ³Ό κ°μ μ λΆλ₯
κΉμ΄ μ°μ νμμ μννλ©΄ κ·Έ κ³Όμ μμ κ·Έλνμ λͺ¨λ κ°μ μ ν λ²μ©μ λ§λκ² λλλ°, μΌλΆ κ°μ λ§μ΄ μ²μ λ°κ²¬ν μ μ κ³Ό μ°κ²°λμ΄ μκΈ°μ μ΄λ₯Ό λ°λΌκ°κ² λλ€. ! νμ§λ§ μ¬κΈ°μ, 무μλλ κ°μ λ€μ ν΅ν΄ κ·Έλνμ ꡬ쑰μ λν μ 보λ₯Ό μ μ μλ€.
μ΄λ ν κ·Έλνμ λν κΉμ΄ μ°μ νμ μ, νμμ΄ λ°λΌκ°λ μΌλΆ κ°μ λ€λ§ λͺ¨μ보면 βνΈλ¦¬β ννλ₯Ό λκ² λλ€. β μ΄μ κ°μ΄ μ»μ΄μ§ νΈλ¦¬λ₯Ό κΉμ΄ μ°μ νμ μ€ν¨λ νΈλ¦¬ νΉμ DFS μ€ν¨λ νΈλ¦¬ λΌκ³ νλ€.
κ°μ μ λΆλ₯
- νΈλ¦¬ κ°μ (tree edge) : μ€ν¨λ νΈλ¦¬μ ν¬ν¨λ κ°μ
- μλ°©ν₯ κ°μ (forward edge) : μ€ν¨λ νΈλ¦¬μ μ μ‘°μμ μμμΌλ‘ μ°κ²°λμμ§λ§ νΈλ¦¬ κ°μ μ΄ μλ κ°μ
- μλ°©ν₯ κ°μ (back edge) : μ€ν¨λ νΈλ¦¬μ μμμμ μ μ‘°λ‘ μ°κ²°λλ κ°μ
- κ΅μ°¨ κ°μ (cross edge) : μμ μΈ κ°μ μ΄ μλ κ°μ , μ μ‘°μ μμ κ΄κ³κ° μλ μ μ λ€ κ° μ°κ²°λ κ°μ
μ΄λ ν μμλ‘ μ μ μ λ°©λ¬Ένλλμ λ°λΌ μλ‘ λ€λ₯Έ νΈλ¦¬κ° λ μλ μκ³ , κ°μ μ λν λΆλ₯κ° λ¬λΌμ§ μλ μλ€.
무ν₯ κ·Έλν κ°μ μ λΆλ₯ 무ν₯ κ·Έλνμ λͺ¨λ κ°μ μ μλ°©ν₯μΌλ‘ ν΅ν κ°λ₯νκΈ° λλ¬Έμ κ΅μ°¨ κ°μ μ΄ μμ μ μλ€. λν, μλ°©ν₯ κ°μ κ³Ό μλ°©ν₯ κ°μ μ ꡬλΆλ μ‘΄μ¬νμ§ μλλ€.
μ¬μ΄ν΄ μ‘΄μ¬ μ¬λΆ νμΈ κ°μ ꡬλΆμ μ΄μ©νμ¬ λ°©ν₯ κ·Έλνμμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλμ§ μ¬λΆλ₯Ό νλ¨ν μ μλ€. β μλ°©ν₯ κ°μ μ μ‘΄μ¬ μ¬λΆμ λμΌν λ¬Έμ
κ°μ μ ꡬλΆνλ λ°©λ²
κ°μ₯ ꡬλΆνκΈ° μ¬μ΄ κ°μ μ νΈλ¦¬ κ°μ μ΄λ€. κ°μ (u, v)λ₯Ό κ²μ¬νμ λ, vκ° λ°©λ¬Έλ μ μ΄ μλ€λ©΄ μ΄λ βνΈλ¦¬ κ°μ βμ΄ λλ€. νμ§λ§ vκ° λ°©λ¬Έλ μ΄νμλ€λ©΄, λΆλͺ¨μΈμ§ μμμΈμ§ μ μ μλ λ°©λ²μ΄ μλ€. κ·Έλμ μΆκ°μ μΈ μ 보λ₯Ό μ μ₯νκ³ μ΄λ₯Ό ν΅ν΄ λΆλͺ¨ μμ κ΄κ³λ₯Ό νμ ν μ μμ΄μΌ νλ€.
- κ° μ μ μ λ°©λ¬Έν λ, μ΄ μ μ μ΄ λ°©λ¬Έλμλ€λ μ¬μ€ =
visited - μ΄ μ μ μ΄ λͺλ²μ§Έλ‘ λ°κ²¬λμλμ§ =
discovered
κ°μ (u, v)μμ uμ vμ λ°©λ¬Έ μμ
- μλ°©ν₯ κ°μ μ΄λΌλ©΄, vλ uμ μμμ΄μ΄μΌ νλ€.
- μλ°©ν₯ κ°μ μ΄λΌλ©΄, vλ uμ μ μ‘°μ¬μΌ νλ€.
- κ΅μ°¨ κ°μ μ΄λΌλ©΄, dfs(v)κ° μ’ λ£ν ν dfs(u)κ° νΈμΆλμ΄μΌ νλ€.
μ κ²½μ° μ€, λ°κ²¬ μμ μ 보λ₯Ό ν λλ‘ μλ°©ν₯ κ°μ μ λν ꡬλΆμ κ°λ₯νμ§λ§, μλ°©ν₯ κ°μ κ³Ό κ΅μ°¨ κ°μ μ λν ꡬλΆμ μ¬μ ν λΆκ°λ₯νλ€. κ·Έλμ, dfs(v)μ μ’ λ£ μ¬λΆ λν νμΈν΄μ£Όμ΄μΌ νλ€.
π λλΉ μ°μ νμ (BFS)
κΉμ΄ μ°μ νμκ³Ό ν¨κ» κ°μ₯ λ리 μ¬μ©λλ κ·Έλν νμ μκ³ λ¦¬μ¦μΌλ‘, "λ€μ΅μ€νΈλΌμ μ΅λ¨ 거리 μκ³ λ¦¬μ¦"μ΄λ "νλ¦Όμ μ΅μ μ€ν¨λ νΈλ¦¬ μκ³ λ¦¬μ¦" λ±μ μ¬μ©λλ€.
βμμμ μμ μ΅μ 거리 κΈ°μ€μΌλ‘ κ°κΉμ΄ μ μ λΆν° μμλλ‘ λ°©λ¬Ένλ νμ μκ³ λ¦¬μ¦βμΌλ‘, μ΅μ λΉμ©μ ꡬν λ μ ν©νλ€.
- κ° μ μ μ λ°©λ¬Έν λλ§λ€ λͺ¨λ μΈμ μ μ λ€μ κ²μ¬
- μ΄ μ€ μ²μ 보λ μ μ μ λ°κ²¬νλ©΄ λ°©λ¬Έ μμ μ΄λΌκ³ κΈ°λ‘νκ³ λ³λμ μμΉμ μ μ₯(
Queue) - μΈμ ν μ μ μ λͺ¨λ κ²μ¬νκ³ λλ©΄, μ§κΈκΉμ§ μ μ₯ν λͺ©λ‘μμ λ€μ μ μ μ κΊΌλ΄μ λ°©λ¬Έ
λλΉ μ°μ νμμ λ°©λ¬Έ μμλ μ μ μ λͺ©λ‘μμ μ΄λ€ μ μ μ λ¨Όμ κΊΌλ΄λμ§μ μν΄ κ²°μ
μμμ μΈκΈν βλ³λμ μμΉβ λ λ¨Όμ λ€μ΄μ¨ μ μ μ λ¨Όμ κΊΌλ΄μΌ νλ νΉμ±μ κ°μ ΈμΌ νλ―λ‘, Queue λ₯Ό μ¬μ©νμ¬ ν΄λΉ 쑰건μ λ§μ‘±μν¨λ€.
κΉμ΄ μ°μ νμκ³Ό λ¬λ¦¬ λλΉ μ°μ νμμμλ λ°κ²¬κ³Ό λ°©λ¬Έμ΄ κ°μ§ μλ€. λ°λΌμ λͺ¨λ μ μ μ
- μμ§ λ°κ²¬λμ§ μμ μν
- λ°κ²¬λμμ§λ§ μμ§ λ°©λ¬Έλμ§λ μμ μν (
Queueμ μ μ₯λ μν) - λ°©λ¬Έλ μν λ‘ 3κ°μ§ μνλ₯Ό κ°μ§ μ μλ€.
κΉμ΄ μ°μ νμμμμ²λΌ, μ μ μ μ λ°κ²¬νλ λ° μ¬μ©νλ κ°μ λ€λ§μ λͺ¨μ νΈλ¦¬λ₯Ό λλΉ μ°μ νμ μ€ν¨λ νΈλ¦¬(BFS Spanning Tree)λΌκ³ νλ€.
π‘ μκ° λ³΅μ‘λ
λͺ¨λ μ μ μ ν λ²μ© λ°©λ¬Ένλ©°, μ μ μ λ°©λ¬Έν λλ§λ€ μΈμ ν λͺ¨λ κ°μ μ κ²μ¬νκΈ° λλ¬Έμ, κΉμ΄ μ°μ νμκ³Ό λμΌνλ€.
π‘ λλΉ μ°μ νμκ³Ό μ΅λ¨ 거리
κ·Έλνμμμ μ΅λ¨ κ²½λ‘ λ¬Έμ λ₯Ό ν΄κ²°νλλ° μ£Όλ‘ μ¬μ©λλ€.
λλΉ μ°μ νμ μκ³ λ¦¬μ¦μ κ°λ¨νκ² λ³κ²½ν΄ λͺ¨λ μ μ μ λν΄ μμμ μΌλ‘λΆν°μ 거리 distance[] λ₯Ό κ³μ°νλλ‘ ν μ μλ€.
- νμ κ³Όμ μμ κ°μ (u, v)λ₯Ό ν΅ν΄ μ μ vλ₯Ό μ²μ λ°κ²¬ν΄
Queueμ λ£λλ€κ³ κ°μ - μμμ μΌλ‘λΆν° vκΉμ§μ μ΅λ¨ 거리
distance[v]λ μμμ μΌλ‘λΆν° uκΉμ§μ μ΅λ¨ 거리distance[u]+1 μ΄λ κ³§ μμμ μΌλ‘λΆν° λ€λ₯Έ λͺ¨λ μ μ κΉμ§μ μ΅λ¨ κ²½λ‘λ₯Ό λλΉ μ°μ νμ μ€ν¨λ νΈλ¦¬ (BFS Spanning Tree) μμ μ°Ύμ μ μλ€λ κ²μ μλ―Ένλ€.
π‘ μλ°©ν₯ νμ
λ μ μ μ¬μ΄μ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύμ λ μ¬μ©ν μ μλ ν ν¬λ μμ μ μ μμ μμνλ μ λ°©ν₯ νμκ³Ό λͺ©ν μ μ μμ μμν΄ κ±°κΎΈλ‘ μ¬λΌμ€λ μλ°©ν₯ νμμ λμμ νλ©΄μ, μ΄ λμ΄ κ°μ΄λ°μ λ§λλ©΄ μ’ λ£
μ΄λ₯Ό μ½λλ‘ κ΅¬ννλ €λ©΄,
μ λ°©ν₯κ³Ό μλ°©ν₯ νμμμ λ°©λ¬Έν΄μΌ ν μ μ λ€μ λͺ¨λ κ°μ Queue μ μ μ₯νλ, μ΅λ¨ 거리λ₯Ό μ μ₯ν λ μ λ°©ν₯μ μμ, μλ°©ν₯μ μμλ‘ μ μ₯νλ€.
μΈμ ν μν κ²μ¬ μ, μλ‘ λΆνΈκ° λ€λ₯΄λ€λ©΄ κ°μ΄λ°μ λ§λ¬μμ νμ
ν μ μλ€.
μλ°©ν₯ νμμ λλΉ μ°μ νμλ³΄λ€ ν¨μ¬ μ μ μ μ λ§μ λ°©λ¬Ένκ³ λ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύμ μ μμ΄ λ©λͺ¨λ¦¬ μ¬μ©λμ΄ ν¨μ¬ μ λ€. νμ§λ§ μ΄λ₯Ό μ¬μ©ν μ μλ κ²½μ°λ, λͺ©ν μ μ κΉμ§μ μ΅λ¨ κ±°λ¦¬κ° λ무 컀μ μλ°©ν₯ νμμΌλ‘λ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύμ μ μλ κ²½μ°λ μ΄λ»κ² ν΄μΌ ν κΉ?
π‘ μ μ κΉμ΄μ§λ νμ
= Iteratively Deepening Search = IDS
- μμμ κΉμ΄ μ ν lμ μ ν ν μ΄ μ νλ³΄λ€ μ§§μ κ²½λ‘κ° μ‘΄μ¬νλμ§λ₯Ό κΉμ΄ μ°μ νμμΌλ‘ νμΈ
- λ΅μ μ°ΎμΌλ©΄ μ±κ³΅, μ΄λ₯Ό λ°ν
- λ΅μ μ°Ύμ§ λͺ»νλ©΄ lμ λλ €μ λ€μ μλ
μ΄λ βμ‘°ν© νμβ κ³Ό κ΄λ ¨μ΄ κΉλ€.
π‘ νμ λ°©λ² μ ννκΈ°
- μν 곡κ°μμμ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύλ κ²½μ°, λλΉ μ°μ νμμ μ°μ μ μΌλ‘ κ³ λ € (μ§κ΄μ μ΄κ³ ꡬνλ κ°λ¨) νμμ κΉμ΄ νκ³κ° μ ν΄μ Έ μμ§ μκ±°λ λ무 κΉμ΄ λ©λͺ¨λ¦¬ μ¬μ©λμ΄ λ무 ν¬μ§ μμμ§μ λν νμΈμ΄ νμ
- μν 곡κ°μμμ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύλλ°, νμμ μ΅λ κΉμ΄κ° μ ν΄μ Έ μκ³ λλΉ μ°μ νμμ νκΈ°μλ λ©λͺ¨λ¦¬μ μκ°μ΄ λΆμ‘±ν κ²½μ°, μλ°©ν₯ νμμ κ³ λ € λͺ©ν μνμμ μλ°©ν₯μΌλ‘ μμ§μ΄κΈ°κ° μ¬μ΄μΌ νλ€.
- λ νμμ΄ λͺ¨λ λ무 λ©λͺ¨λ¦¬λ₯Ό λ§μ΄ μ¬μ©νκ±°λ λ무 λλ¦° κ²½μ°, μ΅μ νλ₯Ό ν κ±°λ¦¬κ° λ λ§μ μ μ κΉμ΄μ§λ νμμ μ¬μ©
π μ°Έκ³
- νλ‘κ·Έλλ° λνμμ λ°°μ°λ μκ³ λ¦¬μ¦ λ¬Έμ ν΄κ²°μ λ΅_κ΅¬μ’ λ§
- Javaκ·Έλνμ νν :: TH